import java.util.*;

public class Reinas
{
    private int tamanyo;                            // Tamanyo del tablero que estamos resolviendo
    private Vector<TableroReinas> soluciones;    // Soluciones encontradas hasta el momento
    
    volatile private long llamadas;                // Numero de llamadas que han sido necesarias
    private long tiempo;                           // Tiempo (en milisegundos) empleado
    
    /**
     *  Busqueda recursiva de soluciones a partir de una solucion parcial, en la que se supone que todas las
     *  columnas anteriores a {@code columna} tienen ya reinas correctamente colocadas. Se supone que la llamada 
     *  recursiva genera todas las soluciones a partir de dicha solucion parcial. Las soluciones son anyadidas
     *  al vector {@code soluciones}, por cuestiones de eficiencia. 
     *  
     *  @param columna Columna a partir de la cual comienza la exploracion recursiva
     *  @param solucion solucion parcial en la que se supone que todas las columnas anteriores a {@code columna}
     *  tienen una reina correctamente colocada.
     */        
    private void analizar_columna(int columna, TableroReinas solucion)
    {
        llamadas++; // Contamos una nueva recursion
       
        // Comprobamos todas las filas de la columna:    
        for (int fila = 0; fila < tamanyo; fila++)    
        {
            // Si la posicion que estamos analizando no es segura, no hay nada mas que hacer.
            // Si por el contrario, es segura...
            if (solucion.posicionSegura(fila, columna))
            {
                // ... colocamos en ella una reina 
                solucion.colocarReina(fila, columna);
                            
                // Si hemos la reina la hemos colocado en la ultima columna tenemos una solucion!    
                if (columna == tamanyo - 1)   
                    soluciones.add(solucion.cloneSolucion());   // Otra solucion al bote, gracias! ;-)
                // En caso contrario, hay que seguir buscando recursivamente posiciones seguras a la derecha...    
                else
                    analizar_columna(columna + 1, solucion);
                                    
                // Backtrack: quitamos la reina que hemos puesto, para seguir buscando 
                // soluciones en las siguientes filas de la misma columna...     
                solucion.quitarReina(columna);
            }    
        }
    }

    /**
     *  Metodo principal de la clase. Genera todas las soluciones para el problema de las N reinas. 
     *  Tras la ejecucion de este metodo, se pueden utilizar los metodos {@code Tiempo} y {@code Llamadas}
     *  para determinar el numero de milisegundos y de llamadas recursivas que han sido necesarias en
     *  el calculo.
     *  
     *  @param tamanyo Tamanyo del tablero sobre el que se colocan las reinas (N, en definitiva).
     *  @return Vector de {@code tableroReinas} con todas las soluciones encontradas.
     */        
    public Vector<TableroReinas> calcularSoluciones(int tamanyo)
    {
        // Antes que nada: ponemos el crono en marcha:
        long inicio = System.currentTimeMillis();
         
        // Anotamos el tamanyo del problema a resolver:
        this.tamanyo = tamanyo;
            
        // Por curiosidad, mas que nada...
        llamadas = 0;
            
        // Inicialmente, no hay ninguna solucion
        soluciones = new Vector<TableroReinas>();
            
        // Y empezamos a buscar soluciones, partiendo de una solucion vacia y empezando por columna 0:
        TableroReinas solucion = new TableroReinas(tamanyo);
        analizar_columna(0, solucion);
            
        // Y hemos terminado. Paramos cronometro:
        tiempo = System.currentTimeMillis()-inicio;
            
        return soluciones;
    }            
        
    /**
     *  Tiempo empleado en la ultima busqueda. 
     *  
     *  @return Numero de milisegundos empleados en la ultima busqueda.
     */    
    public long Tiempo()
    {
        return tiempo;
    }

    /**
     *  Numero de llamadas recursivas efectuadas a {@code analizar_columna} en la ultima busqueda. 
     *  
     *  @return Numero de recursiones ejecutadas en la ultima busqueda.
     */    
    public long Llamadas()
    {
        return llamadas;
    }
}
